//
// Created by 26012 on 2024/10/27.
//
#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;

//建立树结点
typedef struct TNode
{
    ElemType data;             //数据域
    struct TNode* left_child;  //左孩子结点
    struct TNode* right_child;  //右孩子结点
}BTree,*PBTree;

//建立队列辅助层序建树
typedef struct Queue
{
    PBTree tnode;            //指向树的结点
    struct Queue* next;  //队列下一个结点
}Queue,*PQueue;

typedef PBTree ElemType2;

typedef struct LNode{
    ElemType2 data;
    struct LNode* next;
}LinkNode;

typedef struct
{
    LinkNode *front;
    LinkNode *rear;
}LinkQueue;

//初始化链表队列
void Queue_init(LinkQueue &LQ)
{
    //申请一个结点空间，作为链表队列的头节点
    LinkNode* node=(LinkNode*)malloc(sizeof(LinkNode));
    if(NULL == node)
    {
        perror("malloc fail\n");
    }
    node->next=NULL;
    LQ.front=LQ.rear=node;
}

//判断是否为空
bool Queue_empty(LinkQueue &LQ)
{
    return LQ.rear == LQ.front;   //
}

//入队列
void enQueue(LinkQueue &LQ,ElemType2 x)
{
    //为新结点申请一个空间
    LinkNode *node=(LinkNode*)malloc(sizeof(LinkNode));
    if(NULL == node)
    {
        perror("malloc fail\n");
    }
    node->data=x;
    node->next=NULL;
    LQ.rear->next=node;   //链接上新结点
    LQ.rear=node;         //让尾指针指向新的结点
}

//出队列
void deQueue(LinkQueue &LQ,ElemType2 &x)
{
    //判断队列是否为空
    if(Queue_empty(LQ))
    {
        return;
    }
    LinkNode* node=LQ.front->next;  //找到第一个结点
    x=node->data;
    LQ.front->next=node->next;      //断链
    if(LQ.rear == node)
    {
        LQ.rear=LQ.front;   //如果只有一个结点，那rear指针也将指向头结点
    }
    free(node); //释放删除的结点
    node=NULL;
}

//中序遍历
void InOrder(PBTree root)
{
    if(NULL == root)
    {
        return;
    }
    InOrder(root->left_child);
    printf("%c",root->data);
    InOrder(root->right_child);
}

//后序遍历
void PostOrder(PBTree root)
{
    if(NULL == root)
    {
        return;
    }
    PostOrder(root->left_child);
    PostOrder(root->right_child);
    printf("%c",root->data);
}

//层序遍历
void LeverOrder(PBTree root)
{
    //创建链表
    LinkQueue lq;
    Queue_init(lq);
    //记录出队列的结点
    ElemType2 p;
    //入队列
    enQueue(lq,root);
    while(!Queue_empty(lq))
    {
        deQueue(lq,p);
        printf("%c",p->data);
        if(p->left_child)
        {
            enQueue(lq,p->left_child);
        }
        if(p->right_child)
        {
            enQueue(lq,p->right_child);
        }
    }
}

int main()
{
    PBTree root=NULL; //建立根结点指针
    PBTree pNode;     //创建新的树结点的指针
    ElemType c;       //要插入的元素
    //创建辅助队列的头尾指针和当前插入结点指针
    PQueue pcur,ptail;
    while(scanf("%c",&c))
    {
        if('\n' == c){
            break;
        }
        //给树申请一个结点
        pNode=(PBTree)calloc(1,sizeof(BTree));
        pNode->data=c;
        //给队列申请一个空间，并将新结点进队列
        PQueue pqueu=(PQueue)calloc(1,sizeof(Queue));
        pqueu->tnode=pNode;
        //判断树当前是否为NULL
        if(NULL == root)
        {
            root=pNode;
            ptail=pcur=pqueu;
        }
        else{
            ptail->next=pqueu;     //队列结点链接上队列
            ptail=pqueu;           //改变尾指针
            if( NULL == pcur->tnode->left_child)
            {
                pcur->tnode->left_child=pNode;  //新节点连接在父节点的左子树
            }
            else //NULL == pcur->tnode->right_child
            {
                pcur->tnode->right_child=pNode; //新节点连接在父节点的右子树
                pcur=pcur->next;         //当前结点父节点左右孩子均不为空，则移动队列结点
            }
        }
    }
    //中序遍历
    InOrder(root);
    //后序遍历
    printf("\n");
    PostOrder(root);
    //层序遍历
    printf("\n");
    LeverOrder(root);

    return 0;
}